package com.bigshen.algorithm.aLinearList.solution02ReverseLinkedListII;

/**
 *
 ### 92. Reverse Linked List II

 Reverse a linked list from position m to n. Do it in one-pass.

 Note: 1 ≤ m ≤ n ≤ length of list.

 Example:

 Input: 1->2->3->4->5->NULL, m = 2, n = 4
 Output: 1->4->3->2->5->NULL

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {

    public ListNode reverseBetween(ListNode head, int m, int n) {

        if (null == head || null == head.next) {
            return head;
        }

        // 哨兵节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //
        ListNode mNodePrev = dummy;
        ListNode mNode = dummy.next; //2
        ListNode nNode;
        ListNode nNodeNext;
        // 提取m节点mNode 和 m的前一节点mNodePrev
        for (int i = 1; i < m; i++) {
            mNodePrev = mNode;
            mNode = mNode.next;
        }
        // 提取n节点nNode 和 n的后一节点nNodePrev
        nNode = mNode; //2 - 3 - 4
        nNodeNext = nNode.next; //3 - 4 - 5
        for (int i = m; i < n; i++) {
            // m至n反转
            ListNode tmp = nNodeNext.next;
            nNodeNext.next = nNode;
            nNode = nNodeNext;
            nNodeNext = tmp;
        }
        // 重新绑定关系
        mNodePrev.next = nNode; // m前一节点的next指向n
        mNode.next = nNodeNext; // m节点的next执行nNodeNext;

        return dummy.next;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
